/**
 * Created by L.jp
 * Description:假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，
 * 请根据这个价格数组，返回买卖股票能获得的最大收益
 * 1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，
 * 但是再次购买前必须卖出之前的股票
 * 2. 如果不能获取收益，请返回0
 * 3. 假设买入卖出均无手续费
 * User: 86189
 * Date: 2022-09-05
 * Time: 18:32
 */
public class Solution {
    public int maxProfit (int[] prices) {
        int n=prices.length;
        //状态定义，总共有五种状态的收益，没有买过股票的收益，第一次买入的收益，第一次卖出的收益，第二次买入的收益，第二次卖出的收益
        //dp[i][1~4]表示前i天在进行了第几次买入卖出之后的最大收益
        int[][] dp=new int[n][5];
        //第一次买入后的最大收益
        dp[0][1]=-prices[0];
        //第一次卖出后的最大收益
        dp[0][2]=0;  //-prices[0]+prices[0];
        //第二次买入后的最大收益
        dp[0][3]=-prices[0];
        //第二次卖出后的最大收益
        dp[0][4]=0; //-prices[0]+prices[0];
        for(int i=1;i<n;i++){
            //dp[i][0]表示前i天没有买入的最大收益，那么他和前面的状态一样
            //dp[i][0]=dp[i-1][0];
            
            //求前i天的第一次买入的收益，可能是在前面已经买入了，或者是前面没有买入当天刚刚买入，两者收益取最大值
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            //求前i天第一次卖出的收益，可能是前面已经买出了，或者是前面没有卖出只有第一次买入然后当天第一次卖出，两者取最大值
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            //求前i天的第二次买入的收益，可能是在前面已经买入了，或者是前面没有买入当天刚刚买入，两者收益取最大值
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            //求前i天第二次卖出的收益，可能是前面已经买出了，或者是前面没有卖出只有第二次买入然后当天第二次卖出，两者取最大值
            dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        //我们要求的是前n天在第二次卖出后最大收益
        return dp[n-1][4];
    }
}
